// https://leetcode.cn/problems/print-binary-tree/
// Created by ade on 2022/8/22.
//
#include <iostream>
#include <vector>
#include <string>
#include <math.h>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector <vector<string>> res;
    int height = 0;

    vector <vector<string>> printTree(TreeNode *root) {
        height = getHeight(root);
        int len = pow(2, height) - 1;
        res.resize(height, vector<string>(len));
        dfs(root, 0, len / 2);
        return res;
    }

    int getHeight(TreeNode *root) {
        if (!root) return 0;
        return max(getHeight(root->left), getHeight(root->right)) + 1;
    }

    void dfs(TreeNode *root, int row, int col) {
        if (!root) return;
        res[row][col] = to_string(root->val);
        dfs(root->left, row + 1, col - pow(2, height - row - 2));
        dfs(root->right, row + 1, col + pow(2, height - row - 2));
    }

    TreeNode *init() {
        TreeNode *head1 = new TreeNode(1);
        TreeNode *head2 = new TreeNode(2);
        TreeNode *head3 = new TreeNode(3);
        TreeNode *head4 = new TreeNode(4);
//        TreeNode *head4 = new TreeNode(3);
//        TreeNode *head5 = new TreeNode(3);
//        TreeNode *head6 = new TreeNode(4);
//        TreeNode *head7 = new TreeNode(4);
        head1->left = head2;
//        head1->right = head3;
        head1->right = head3;
        head2->right = head4;
//
//        head3->left = nullptr;
//        head3->right = nullptr;
//        head4->left = head6;
//        head4->right = head6;
        return head1;
    }
};

/*
 * [["","","","1","","",""] // 0 -     3
 * ,["","2","","","","3",""] // 1 - 1     5
 * ,["","","4","","","",""]]//2       2
 *
 * */

int main() {
    Solution so;
    TreeNode *head = so.init();
    auto res = so.printTree(head);
    for (auto items : res) {
        cout << "[";
        for (auto i : items) {
            if (i != "") {
                cout << "\"" << i << "\"" << ",";
            } else {
                cout << "\"\"" << ",";
            }

        }
        cout << "]" << endl;
    }
    return 0;
}